package com.wc.alorithm_blue_bridge._数学知识.快速幂.Q1514;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * @Author congege
 * @Description
 * @Date Created in 2023/11/24-22:43
 */
public class Main2 {
    public static void main(String[] args) {
        Input sc = new Input();
        int n = sc.nextInt();
        while (n-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            System.out.println(quick(a, b, c));
        }
    }

    static long quick(long a, long b, long c) {
        if (b == 1) {
            return a % c;
        }
        long qk = quick(a, b / 2, c) % c;

        if (b % 2 == 1) {
            return qk * qk % c * a % c;
        }
        return qk * qk % c;
    }

    static class Input {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }
}
